package shortestToChar;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public int[] shortestToChar(String s, char c) {
//        List<Integer> list = new ArrayList<>();
//        for (int i = 0; i < s.length(); i++) {
//            if(s.charAt(i) == c){
//                list.add(i);
//            }
//        }
//        int[] ans = new int[s.length()];
//        for (int i = 0; i < ans.length; i++) {
//            for (int index: list) {
//                ans[i] = Math.min(Math.abs(i-index),ans[i]);
//            }
//        }
//        return ans;

        // 双指针
//        int l = -10000;
//        int r = 0;
//        for (int i = 0; i < s.length(); i++) {
//            if(s.charAt(i)==c){
//                r = i;
//                break;
//            }
//        } // 找到第一个字母c
//        int[] ans = new int[s.length()];
//        for (int i = 0; i < s.length(); i++) {
//            if(s.charAt(i) == c){
//                l = c;
//                while(r<s.length()&&s.charAt(r)!=c){
//                    r++;
//                }
//                if(r==s.length()){
//                    r = 200000;
//                }
//            }
//            ans[i] = Math.min(i-l,r-i);
//        }
//        return ans;
        int[] ans = new int[s.length()];
        for (int i = 0,index = -s.length(); i < s.length(); i++) {
            if(s.charAt(i) == c){
                index = i;
            }
            ans[i] = i - index;
        } // 左面离的最近的
        for (int i = s.length()-1,index = 2*s.length(); i >= 0; i--) {
            if(s.charAt(i) == c){
                index = i;
            }
            ans[i] = Math.min(ans[i],index-i);
        }// 右面最近的
        return ans;
    }
}

// 左扫右扫
//class Solution {
//    public int[] shortestToChar(String s, char c) {
//        int n = s.length();
//        int[] ans = new int[n];
//
//        for (int i = 0, idx = -n; i < n; ++i) {
//            if (s.charAt(i) == c) {
//                idx = i;
//            }
//            ans[i] = i - idx;
//        }
//
//        for (int i = n - 1, idx = 2 * n; i >= 0; --i) {
//            if (s.charAt(i) == c) {
//                idx = i;
//            }
//            ans[i] = Math.min(ans[i], idx - i);
//        }
//        return ans;
//    }
//}